

In [1]:

    
push!(LOAD_PATH,"../src")
using Laplacians



In [2]:

    
n = 10;
A = randRegular(n,5)
A = triu(A);
full(A)









    Out[2]:





10x10 Array{Float64,2}:
 0.0  2.0  1.0  0.0  2.0  0.0  0.0  0.0  0.0  0.0
 0.0  0.0  1.0  0.0  0.0  2.0  0.0  0.0  0.0  0.0
 0.0  0.0  0.0  1.0  0.0  0.0  0.0  0.0  0.0  2.0
 0.0  0.0  0.0  0.0  1.0  0.0  2.0  0.0  1.0  0.0
 0.0  0.0  0.0  0.0  0.0  0.0  0.0  1.0  1.0  0.0
 0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  2.0  1.0
 0.0  0.0  0.0  0.0  0.0  0.0  0.0  2.0  0.0  1.0
 0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  1.0  1.0
 0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0
 0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0



In [3]:

    
rInd = randperm(n);
rA = A[rInd,rInd];
full(rA)









    Out[3]:





10x10 Array{Float64,2}:
 0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0
 1.0  0.0  2.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0
 0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0
 0.0  0.0  1.0  0.0  0.0  1.0  0.0  0.0  0.0  0.0
 0.0  0.0  1.0  1.0  0.0  0.0  0.0  2.0  0.0  0.0
 1.0  0.0  1.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0
 2.0  0.0  0.0  0.0  1.0  0.0  0.0  0.0  0.0  0.0
 1.0  0.0  0.0  0.0  0.0  2.0  0.0  0.0  0.0  0.0
 0.0  0.0  0.0  2.0  0.0  0.0  1.0  0.0  0.0  2.0
 0.0  2.0  0.0  0.0  0.0  0.0  1.0  0.0  0.0  0.0



In [4]:

    
B = dirEdgeVertexMat(A)';
B'*collect(1:n) .< 0









    Out[4]:





18-element BitArray{1}:
 true
 true
 true
 true
 true
 true
 true
 true
 true
 true
 true
 true
 true
 true
 true
 true
 true
 true



In [5]:

    
B = dirEdgeVertexMat(rA)';
B'*collect(1:n) .< 0









    Out[5]:





18-element BitArray{1}:
 false
 false
 false
 false
 false
  true
 false
 false
 false
 false
 false
 false
  true
 false
 false
 false
  true
  true

Let's figure out how to first see that mat a is a DAG, then sort it in a way that proves it, (orig order should work), then sort it in a way that's not a topological sort, then use toposort to get back another topoorder.



In [6]:

    
topoOrd = toposort(A)









    Out[6]:





10-element Array{Int64,1}:
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10



In [7]:

    
Atopo = A[topoOrd,topoOrd];
Btopo = dirEdgeVertexMat(Atopo)';



In [8]:

    
Btopo'*collect(1:n) .< 0









    Out[8]:





18-element BitArray{1}:
 true
 true
 true
 true
 true
 true
 true
 true
 true
 true
 true
 true
 true
 true
 true
 true
 true
 true



In [16]:

    
rtopoOrd = toposort(rA);
rAtopo = rA[rtopoOrd,rtopoOrd];
rBtopo = dirEdgeVertexMat(rAtopo)';
rBtopo'*collect(1:n) .< 0









    Out[16]:





20-element BitArray{1}:
 true
 true
 true
 true
 true
 true
 true
 true
 true
 true
 true
 true
 true
 true
 true
 true
 true
 true
 true
 true

good!

Now, let's try a graph that doesn't have a topoOrder, just to make sure?



In [47]:

    
uA = randRegular(n,5)
utopoOrd = toposort(uA');
uAtopo = uA[utopoOrd,utopoOrd];
uBtopo = dirEdgeVertexMat(uAtopo')';
uBtopo'*collect(1:n) .< 0









    Out[47]:





44-element BitArray{1}:
 false
 false
 false
 false
 false
  true
 false
 false
 false
 false
 false
 false
 false
     ⋮
  true
 false
  true
  true
  true
  true
 false
  true
  true
  true
  true
  true

good, there'd be something wrong if all edges respected the non-existent topo order?